package lianbiao

import tp "hufeng/type-practice"

func reverseList(head *tp.ListNode) *tp.ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	return reverse(head, head.Next)
}

func reverse(a *tp.ListNode, b *tp.ListNode) *tp.ListNode {
	if b.Next == nil {
		b.Next = a
		return b
	}
	c := b.Next
	newHead := reverse(b, c)
	b.Next = a
	return newHead
}

func ReverseHead(head *tp.ListNode) *tp.ListNode {
	// 到达头或者尾
	if head == nil || head.Next == nil {
		return head
	}
	// 深层递归，直至结束
	NewHead := ReverseHead(head.Next)
	// 进行指针修改，出栈
	head.Next.Next = head
	head.Next = nil
	return NewHead
}

func TwoPoint(head *tp.ListNode) *tp.ListNode {
	pre := &tp.ListNode{}
	pre.Next = head
	cur := head
	for cur != nil {
		a := cur.Next
		cur.Next = pre
		pre = cur
		cur = a
	}
	return pre
}
